`
https://leetcode.cn/problems/target-sum/
`

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function (nums, target) {
  const sum = nums.reduce((acc, cur) => acc + cur, 0)
  // 这两种情况，不可能存在合法的子集划分
  if (sum < Math.abs(target) || (sum + target) % 2 === 1) {
    return 0;
  }
  // 思路参考：https://labuladong.online/algo/dynamic-programming/target-sum/#%E4%B8%89%E3%80%81%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98
  return subsets(nums, (sum + target) / 2);
};

// 计算 nums 中有几个子集的和为 sum
var subsets = function (nums, sum) {
  var n = nums.length;
  var dp = new Array(sum + 1).fill(0);
  // base case
  dp[0] = 1;

  for (var i = 1; i <= n; i++) {
    // j 要从后往前遍历
    for (var j = sum; j >= 0; j--) {
      // 状态转移方程
      if (j >= nums[i - 1]) {
        dp[j] = dp[j] + dp[j - nums[i - 1]];
      } else {
        dp[j] = dp[j];
      }
    }
  }
  return dp[sum];
};